package Demo2_28;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-02-28
 * Time:23:34
 */
import java.util.Arrays;

public class KSmallestNumbers {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (arr == null || arr.length == 0 || k == 0) {
            return new int[0];
        }
        quickSelect(arr, 0, arr.length - 1, k - 1);
        return Arrays.copyOf(arr, k);
    }

    private void quickSelect(int[] arr, int left, int right, int k) {
        if (left >= right) {
            return;
        }
        int pivotIndex = partition(arr, left, right);
        if (pivotIndex == k) {
            return;
        } else if (pivotIndex > k) {
            quickSelect(arr, left, pivotIndex - 1, k);
        } else {
            quickSelect(arr, pivotIndex + 1, right, k);
        }
    }

    private int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                swap(arr, i, j);
                i++;
            }
        }
        swap(arr, i, right);
        return i;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        KSmallestNumbers solution = new KSmallestNumbers();
        int[] arr = {3, 2, 1};
        int k = 2;
        int[] result = solution.getLeastNumbers(arr, k);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}